//package com.algo.QFS;
//
///**
// * @Author: guoxing
// * @Email: gx_study2022@163.com
// * @Description: https://blog.csdn.net/weixin_37980595/article/details/125358520
// * @Date: 2024/6/24 22:37
// * @ClassName: Qfs
// **/
//public class Qfs {
//    /**
//     * 启发策略-最早开始时间
//     */
//    private void EST(){
//        while (true) {
//            //遍历工件
//            for (int i = 0; i < data.workId.length; i++) {
//                //选取工序i的剩余第一个工序
//                if (workProcess.get(i).size() != 0) {
//                    //System.out.println("=======工件"+(i+1)+"|工序"+workProcess.get(i).get(0)+"=======");
//                    //随机生成设备遍历顺序
//                    int[] orderArr = new int[data.deviceId.length];
//                    for (int j = 0; j < data.deviceId.length; j++) orderArr[j] = j;
//                    shuffle(orderArr);
//                    //找到开始时间最短的机器设备
//                    int deviceIndex = data.deviceId.length;
//                    double deviceTime = Double.MAX_VALUE;
//                    //随机遍历机器
//                    for (int j = 0; j < data.deviceId.length; j++) {
//                        //工序只能在可加工设备上进行加工
//                        if (data.ProcessTime[i][workProcess.get(i).get(0) - 1][orderArr[j]] != Double.MAX_VALUE) {
//                            if (workResult.get(orderArr[j]).size() == 0) {
//                                //下一工序的开始时间大于等于上一工序的结束时间
//                                if (workProcess.get(i).get(0) == 1) {
//                                    //第一个工序
//                                    deviceTime = 0;
//                                    deviceIndex = orderArr[j];
//                                    //System.out.println("遍历设备"+(orderArr[j]+1)+"\t"+"目标设备"+(deviceIndex+1)+"\t"+deviceTime);
//                                    break;
//                                }
//                            } else {
//                                if (workProcess.get(i).get(0) == 1) {
//                                    if (workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime < deviceTime) {
//                                        deviceTime = workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime+1;
//                                        deviceIndex = orderArr[j];
//                                    }
//                                } else {
//                                    if (workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime < deviceTime) {
//                                        if (workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime >= endTime[i][workProcess.get(i).get(0) - 2]) {
//                                            deviceTime = workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime+1;
//                                            deviceIndex = orderArr[j];
//                                        }
//                                        if (workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime < endTime[i][workProcess.get(i).get(0) - 2]) {
//                                            deviceTime = endTime[i][workProcess.get(i).get(0) - 2]+1;
//                                            deviceIndex = orderArr[j];
//                                        }
//                                    }
//                                }
//                            }
//                        }
//                        //System.out.println("遍历设备"+(orderArr[j]+1)+"\t"+"目标设备"+(deviceIndex+1)+"\t"+deviceTime);
//                    }
//                    //更新工件信息
//                    if (deviceIndex != data.deviceId.length) {
//                        shop.workId = i + 1;
//                        shop.workProcess = workProcess.get(i).get(0);
//                        shop.deviceId = deviceIndex + 1;
//                        shop.startTime = deviceTime;
//                        startTime[i][workProcess.get(i).get(0) - 1] = shop.startTime;
//                        //System.out.println(i + "\t" + (workProcessTemp.get(i).get(0) - 1) + "\t" + deviceIndex);
//                        shop.endTime = shop.startTime + data.ProcessTime[i][workProcess.get(i).get(0) - 1][deviceIndex];
//                        endTime[i][workProcess.get(i).get(0) - 1] = shop.endTime;
//                        //工件信息加入结果列表
//                        workResult.get(deviceIndex).add(shop.clone());
//                        //删除该工序
//                        workProcess.get(i).remove(0);
//                    }
//                }
//            }
//            //所有工序分配完毕时，结束
//            boolean stopCondition = true;
//            for (int i = 0; i < data.workId.length; i++) {
//                if (workProcess.get(i).size() != 0) {
//                    stopCondition = false;
//                    break;
//                }
//            }
//            if (stopCondition) break;
//        }
//        printResult(workResult,endTime);
//    }
//    /**
//     * 贪婪启发策略-最早开始时间
//     * 匈牙利算法分配第一工序和设备
//     */
//    private void GEST(){
//        //第一个工序分配
//        int[] assignResult=shopAssign(data.ProcessTime);
//        //分配第一个工序
//        for(int i=0;i<assignResult.length;i++){
//            int deviceIndex = data.deviceId.length;
//            double deviceTime = Double.MAX_VALUE;
//            if (workProcess.get(i).size() != 0){
//                if (workResult.get(assignResult[i]-1).size() == 0){
//                    deviceTime = 0;
//                    deviceIndex = assignResult[i]-1;
//                }
//                else{
//                    deviceTime = workResult.get(assignResult[i]-1).get(workResult.get(assignResult[i]-1).size() - 1).endTime+1;
//                    deviceIndex = assignResult[i]-1;
//                }
//            }
//            if (deviceIndex != data.deviceId.length) {
//                shop.workId = i + 1;
//                shop.workProcess = workProcess.get(i).get(0);
//                shop.deviceId = deviceIndex + 1;
//                shop.startTime = deviceTime;
//                startTime[i][workProcess.get(i).get(0) - 1] = shop.startTime;
//                shop.endTime = shop.startTime + data.ProcessTime[i][workProcess.get(i).get(0) - 1][deviceIndex];
//                endTime[i][workProcess.get(i).get(0) - 1] = shop.endTime;
//                workResult.get(deviceIndex).add(shop.clone());
//                workProcess.get(i).remove(0);
//            }
//        }
//        //分配其余工序
//        while (true) {
//            //遍历工件
//            for (int i = 0; i < data.workId.length; i++) {
//                //选取工序i的剩余第一个工序
//                if (workProcess.get(i).size() != 0) {
//                    //System.out.println("=======工件"+(i+1)+"|工序"+workProcess.get(i).get(0)+"=======");
//                    //随机生成设备遍历顺序
//                    int[] orderArr = new int[data.deviceId.length];
//                    for (int j = 0; j < data.deviceId.length; j++) orderArr[j] = j;
//                    shuffle(orderArr);
//                    //找到开始时间最短的机器设备
//                    int deviceIndex = data.deviceId.length;
//                    double deviceTime = Double.MAX_VALUE;
//                    //随机遍历机器
//                    for (int j = 0; j < data.deviceId.length; j++) {
//                        //工序只能在可加工设备上进行加工
//                        if (data.ProcessTime[i][workProcess.get(i).get(0) - 1][orderArr[j]] != Double.MAX_VALUE) {
//                            if (workResult.get(orderArr[j]).size() == 0) {
//                                //下一工序的开始时间大于等于上一工序的结束时间
//                                if (workProcess.get(i).get(0) == 1) {
//                                    //第一个工序
//                                    deviceTime = 0;
//                                    deviceIndex = orderArr[j];
//                                    //System.out.println("遍历设备"+(orderArr[j]+1)+"\t"+"目标设备"+(deviceIndex+1)+"\t"+deviceTime);
//                                    break;
//                                }
//                            } else {
//                                if (workProcess.get(i).get(0) == 1) {
//                                    if (workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime < deviceTime) {
//                                        deviceTime = workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime+1;
//                                        deviceIndex = orderArr[j];
//                                    }
//                                } else {
//                                    if (workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime < deviceTime) {
//                                        if (workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime >= endTime[i][workProcess.get(i).get(0) - 2]) {
//                                            deviceTime = workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime+1;
//                                            deviceIndex = orderArr[j];
//                                        }
//                                        if (workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime < endTime[i][workProcess.get(i).get(0) - 2]) {
//                                            deviceTime = endTime[i][workProcess.get(i).get(0) - 2]+1;
//                                            deviceIndex = orderArr[j];
//                                        }
//                                    }
//                                }
//                            }
//                        }
//                        //System.out.println("遍历设备"+(orderArr[j]+1)+"\t"+"目标设备"+(deviceIndex+1)+"\t"+deviceTime);
//                    }
//                    //更新工件信息
//                    if (deviceIndex != data.deviceId.length) {
//                        shop.workId = i + 1;
//                        shop.workProcess = workProcess.get(i).get(0);
//                        shop.deviceId = deviceIndex + 1;
//                        shop.startTime = deviceTime;
//                        startTime[i][workProcess.get(i).get(0) - 1] = shop.startTime;
//                        //System.out.println(i + "\t" + (workProcessTemp.get(i).get(0) - 1) + "\t" + deviceIndex);
//                        shop.endTime = shop.startTime + data.ProcessTime[i][workProcess.get(i).get(0) - 1][deviceIndex];
//                        endTime[i][workProcess.get(i).get(0) - 1] = shop.endTime;
//                        //工件信息加入结果列表
//                        workResult.get(deviceIndex).add(shop.clone());
//                        //删除该工序
//                        workProcess.get(i).remove(0);
//                    }
//                }
//            }
//            //所有工序分配完毕时，结束
//            boolean stopCondition = true;
//            for (int i = 0; i < data.workId.length; i++) {
//                if (workProcess.get(i).size() != 0) {
//                    stopCondition = false;
//                    break;
//                }
//            }
//            if (stopCondition) break;
//        }
//        printResult(workResult,endTime);
//    }
//
//    /**
//     * 启发策略-最早结束时间
//     * 随机分配工序
//     */
//    private void EET(){
//        while (true) {
//            //遍历工件
//            for (int i = 0; i < data.workId.length; i++) {
//                //选取工序i的剩余第一个工序
//                if (workProcess.get(i).size() != 0) {
//                    //System.out.println("=======工件"+(i+1)+"|工序"+workProcess.get(i).get(0)+"=======");
//                    //随机生成设备遍历顺序
//                    int[] orderArr = new int[data.deviceId.length];
//                    for (int j = 0; j < data.deviceId.length; j++) orderArr[j] = j;
//                    shuffle(orderArr);
//                    //找到开始时间最短的机器设备
//                    int deviceIndex = data.deviceId.length;
//                    double deviceTime = Double.MAX_VALUE;
//                    //随机遍历机器
//                    for (int j = 0; j < data.deviceId.length; j++) {
//                        //工序只能在可加工设备上进行加工
//                        if (data.ProcessTime[i][workProcess.get(i).get(0) - 1][orderArr[j]] != Double.MAX_VALUE) {
//                            if (workResult.get(orderArr[j]).size() == 0) {
//                                //下一工序的开始时间大于等于上一工序的结束时间
//                                if (workProcess.get(i).get(0) == 1) {
//                                    //第一个工序
//                                    deviceTime = data.ProcessTime[i][workProcess.get(i).get(0)-1][orderArr[j]];
//                                    deviceIndex = orderArr[j];
//                                    break;
//                                }
//                            } else {
//                                if (workProcess.get(i).get(0) == 1) {
//                                    if (workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime+1+data.ProcessTime[i][workProcess.get(i).get(0)-1][orderArr[j]] < deviceTime) {
//                                        deviceTime = workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime+1+data.ProcessTime[i][workProcess.get(i).get(0)-1][orderArr[j]];
//                                        deviceIndex = orderArr[j];
//                                    }
//                                } else {
//                                    if (workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime+1+data.ProcessTime[i][workProcess.get(i).get(0)-1][orderArr[j]]< deviceTime) {
//                                        if (workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime >= endTime[i][workProcess.get(i).get(0) - 2]) {
//                                            deviceTime = workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime+1+data.ProcessTime[i][workProcess.get(i).get(0)-1][orderArr[j]];
//                                            deviceIndex = orderArr[j];
//                                        }
//                                        if (workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime < endTime[i][workProcess.get(i).get(0) - 2]) {
//                                            deviceTime = endTime[i][workProcess.get(i).get(0) - 2]+1+data.ProcessTime[i][workProcess.get(i).get(0)-1][orderArr[j]];
//                                            deviceIndex = orderArr[j];
//                                        }
//                                    }
//                                }
//                            }
//                        }
//                        //System.out.println("遍历设备"+(orderArr[j]+1)+"\t"+"目标设备"+(deviceIndex+1)+"\t"+deviceTime);
//                    }
//                    //更新工件信息
//                    if (deviceIndex != data.deviceId.length) {
//                        shop.workId = i + 1;
//                        shop.workProcess = workProcess.get(i).get(0);
//                        shop.deviceId = deviceIndex + 1;
//                        shop.endTime = deviceTime;
//                        endTime[i][workProcess.get(i).get(0) - 1] = shop.endTime;
//                        shop.startTime = shop.endTime - data.ProcessTime[i][workProcess.get(i).get(0) - 1][deviceIndex];;
//                        startTime[i][workProcess.get(i).get(0) - 1] = shop.startTime;
//                        //工件信息加入结果列表
//                        workResult.get(deviceIndex).add(shop.clone());
//                        //删除该工序
//                        workProcess.get(i).remove(0);
//                    }
//                }
//            }
//            //所有工序分配完毕时，结束
//            boolean stopCondition = true;
//            for (int i = 0; i < data.workId.length; i++) {
//                if (workProcess.get(i).size() != 0) {
//                    stopCondition = false;
//                    break;
//                }
//            }
//            if (stopCondition) break;
//        }
//        printResult(workResult,endTime);
//    }
//
//    /**
//     * 贪婪启发策略-最早结束时间
//     * 匈牙利算法分配第一工序和设备
//     */
//    private void GEET(){
//        //第一个工序分配
//        int[] assignResult=shopAssign(data.ProcessTime);
//        //分配第一个工序
//        for(int i=0;i<assignResult.length;i++){
//            int deviceIndex = data.deviceId.length;
//            double deviceTime = Double.MAX_VALUE;
//            if (workProcess.get(i).size() != 0){
//                if (workResult.get(assignResult[i]-1).size() == 0){
//                    deviceTime = data.ProcessTime[i][workProcess.get(i).get(0)-1][assignResult[i]-1];
//                    deviceIndex = assignResult[i]-1;
//                }
//                else{
//                    deviceTime = workResult.get(assignResult[i]-1).get(workResult.get(assignResult[i]-1).size() - 1).endTime+1+data.ProcessTime[i][workProcess.get(i).get(0)-1][assignResult[i]-1];
//                    deviceIndex = assignResult[i]-1;
//                }
//            }
//            if (deviceIndex != data.deviceId.length) {
//                shop.workId = i + 1;
//                shop.workProcess = workProcess.get(i).get(0);
//                shop.deviceId = deviceIndex + 1;
//                shop.endTime = deviceTime;
//                endTime[i][workProcess.get(i).get(0) - 1] = shop.endTime;
//                shop.startTime = shop.endTime - data.ProcessTime[i][workProcess.get(i).get(0) - 1][deviceIndex];;
//                startTime[i][workProcess.get(i).get(0) - 1] = shop.startTime;
//                workResult.get(deviceIndex).add(shop.clone());
//                workProcess.get(i).remove(0);
//            }
//        }
//        //分配其余工序
//        while (true) {
//            //遍历工件
//            for (int i = 0; i < data.workId.length; i++) {
//                //选取工序i的剩余第一个工序
//                if (workProcess.get(i).size() != 0) {
//                    //System.out.println("=======工件"+(i+1)+"|工序"+workProcess.get(i).get(0)+"=======");
//                    //随机生成设备遍历顺序
//                    int[] orderArr = new int[data.deviceId.length];
//                    for (int j = 0; j < data.deviceId.length; j++) orderArr[j] = j;
//                    shuffle(orderArr);
//                    //找到开始时间最短的机器设备
//                    int deviceIndex = data.deviceId.length;
//                    double deviceTime = Double.MAX_VALUE;
//                    //随机遍历机器
//                    for (int j = 0; j < data.deviceId.length; j++) {
//                        //工序只能在可加工设备上进行加工
//                        if (data.ProcessTime[i][workProcess.get(i).get(0) - 1][orderArr[j]] != Double.MAX_VALUE) {
//                            if (workResult.get(orderArr[j]).size() == 0) {
//                                //下一工序的开始时间大于等于上一工序的结束时间
//                                if (workProcess.get(i).get(0) == 1) {
//                                    //第一个工序
//                                    deviceTime = data.ProcessTime[i][workProcess.get(i).get(0)-1][orderArr[j]];
//                                    deviceIndex = orderArr[j];
//                                    break;
//                                }
//                            } else {
//                                if (workProcess.get(i).get(0) == 1) {
//                                    if (workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime+1+data.ProcessTime[i][workProcess.get(i).get(0)-1][orderArr[j]] < deviceTime) {
//                                        deviceTime = workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime+1+data.ProcessTime[i][workProcess.get(i).get(0)-1][orderArr[j]];
//                                        deviceIndex = orderArr[j];
//                                    }
//                                } else {
//                                    if (workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime+1+data.ProcessTime[i][workProcess.get(i).get(0)-1][orderArr[j]]< deviceTime) {
//                                        if (workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime >= endTime[i][workProcess.get(i).get(0) - 2]) {
//                                            deviceTime = workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime+1+data.ProcessTime[i][workProcess.get(i).get(0)-1][orderArr[j]];
//                                            deviceIndex = orderArr[j];
//                                        }
//                                        if (workResult.get(orderArr[j]).get(workResult.get(orderArr[j]).size() - 1).endTime < endTime[i][workProcess.get(i).get(0) - 2]) {
//                                            deviceTime = endTime[i][workProcess.get(i).get(0) - 2]+1+data.ProcessTime[i][workProcess.get(i).get(0)-1][orderArr[j]];
//                                            deviceIndex = orderArr[j];
//                                        }
//                                    }
//                                }
//                            }
//                        }
//                        //System.out.println("遍历设备"+(orderArr[j]+1)+"\t"+"目标设备"+(deviceIndex+1)+"\t"+deviceTime);
//                    }
//                    //更新工件信息
//                    if (deviceIndex != data.deviceId.length) {
//                        shop.workId = i + 1;
//                        shop.workProcess = workProcess.get(i).get(0);
//                        shop.deviceId = deviceIndex + 1;
//                        shop.endTime = deviceTime;
//                        endTime[i][workProcess.get(i).get(0) - 1] = shop.endTime;
//                        shop.startTime = shop.endTime - data.ProcessTime[i][workProcess.get(i).get(0) - 1][deviceIndex];;
//                        startTime[i][workProcess.get(i).get(0) - 1] = shop.startTime;
//                        //工件信息加入结果列表
//                        workResult.get(deviceIndex).add(shop.clone());
//                        //删除该工序
//                        workProcess.get(i).remove(0);
//                    }
//                }
//            }
//            //所有工序分配完毕时，结束
//            boolean stopCondition = true;
//            for (int i = 0; i < data.workId.length; i++) {
//                if (workProcess.get(i).size() != 0) {
//                    stopCondition = false;
//                    break;
//                }
//            }
//            if (stopCondition) break;
//        }
//        printResult(workResult,endTime);
//    }
//
//}
